class Solution {
public:
    bool check[16]={0};
    int ret=0;
    int tem;
    int countArrangement(int n) {
        tem=n;
        dfs(1);
        return ret;
    }

    void dfs(int p)
    {
        if(p==tem+1) 
        {
            ret++;
            return;
        }
        for(int i=1;i<=tem;i++)
        {
            if(!check[i]&&(i%p==0||p%i==0))
            {
                check[i]=true;
                dfs(p+1);
                check[i]=false;
            }
        }
    }
};